package leecoke;

import java.util.ArrayList;

public class Test024 {
    public static class ListNode{
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    // 递归方式
    public static ListNode swapPairs(ListNode head) {
        // 为空或者只有一个节点不需要交换
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

    public static ListNode swapPairs1(ListNode head) {
        // 为空或者只有一个节点不需要交换
        if (head == null || head.next == null) {
            return head;
        }
        // 哨兵接节点
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        ListNode temp = dumpy;
        // 每次交换的第一个节点
        ListNode start = null;
        // 每次交换的第二个节点
        ListNode end = null;
        while (temp.next != null && temp.next.next != null) {
            start = temp.next;
            end = temp.next.next;
            temp.next = end;
            // 连接后续节点
            start.next = end.next;
            // 将 start 指向下一次交换的第一个节点
            end.next = start;
            // 整总指针
            temp = start;
        }
        return dumpy.next;
    }

    public static ListNode swapPairs2(ListNode head) {
        // 为空或者只有一个节点不需要交换
        if (head == null || head.next == null) {
            return head;
        }
        // 统计链表长度，用于创建数组
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        ListNode[] arr = new ListNode[size];
        // 添加到数组中时，注意需要打断后续，不然重组的时候会出现问题
        cur = head;
        ListNode temp = null;
        for (int i = 0; i < arr.length; i++) {
            temp = cur.next;
            cur.next = null;
            arr[i] = cur;
            cur = temp;
        }
        int  len = arr.length;
        for (int i = 0; i < len; i++) {
            // 偶数个则全部交换，技术个最后一个元素不换
            if (i + 1 < len) {
                swap(arr, i, ++i);
            }
        }
        // 重组链表
        for (int i = 1; i < size; i++) {
            arr[i - 1].next = arr[i];
        }
        return arr[0];
    }

    public static void swap(ListNode[] arr, int i, int j) {
        ListNode temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        printNode(head);
        ListNode listNode = swapPairs(head);
        System.out.println("====================");
        printNode(listNode);
        System.out.println("====================");
    }

    public static void printNode(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}
